`
https://leetcode.cn/problems/n-queens/
`

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
  const res = []

  const board = new Array(n).fill(null).map(() => '.'.repeat(n))

  const backtrack = (row) => {
    if (row === n) {
      // 找到一个解
      res.push(Array.from(board))
      return
    }

    for (let col = 0; col < n; col++) {
      if (!isValid(board, row, col)) {
        continue
      }

      // 做选择
      board[row] = board[row].substring(0, col) + 'Q' + board[row].substring(col + 1);

      backtrack(row + 1)

      // 取消选择
      board[row] = board[row].substring(0, col) + '.' + board[row].substring(col + 1);
    }
  }

  backtrack(0)
  return res
};

function isValid(board, row, col) {
  // 因为我们是从上往下放置皇后的，
  // 所以只需要检查上方是否有皇后互相冲突，
  // 不需要检查下方

  const n = board.length;

  // 检查列是否有皇后互相冲突
  for (let i = 0; i < row; i++) {
    if (board[i][col] === 'Q') {
      return false;
    }
  }

  // 检查右上方是否有皇后互相冲突
  for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
    if (board[i][j] === 'Q') {
      return false;
    }
  }

  // 检查左上方是否有皇后互相冲突
  for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
    if (board[i][j] === 'Q') {
      return false;
    }
  }

  return true;
}